Path search is widely used in several areas, for example, to move a robot to a destination position for service provision, to move artificial intelligence units in a computer game, to determine a path of an unmanned surveillance plane, and the like.
In path search algorithms, search time reduction and optimal path search are two major factors.
Meanwhile, real-time path search is required when a set path of a mobile object needs to be changed based on surrounding information detected while moving, due to incompleteness of given map information used in setting the path, an encounter with a mobile obstacle such as a person while moving along the set path, and a deviation from the set path caused by control errors, for example. In particular, when the mobile object encounters the mobile obstacle or when the given map information does not match with the surrounding information detected while the mobile object is actually moving, a delay in searching a new path may cause a delay in the movement of the mobile object. Thus, there is a need for a fast path search method.
Further, in computer games, fast path search algorithm is required in order to find and control paths of a number of units simultaneously.
A* algorithm based on a grid map is a conventional path search algorithm. The A* algorithm always secures to find an optimal path from a starting position to a destination position. However, it is difficult to use the A* algorithm in real-time path search due to its high computational cost.
Further, the A* algorithm has a drawback in that a path search time increases by geometric progression with an increase of a map size.
Researches have been made to improve a search time of the A* algorithm, and representative examples thereof include an Anytime A* algorithm and a Dynamic A* algorithm.
The Anytime A* algorithm was designed to find the best possible solution within a given time limit. In the Anytime A*, path search using the A* algorithm is first performed under relaxed best solution conditions to obtain a rough path, and then if the time remains, the path search is performed again under tightened best solution conditions in comparison with those used before to obtain a path nearer to the best solution than the path obtained before. In the Anytime A* algorithm, the path search using the A* algorithm would be repeatedly performed until the given time is used up.
In the Dynamic A* algorithm, a path from a starting position to a destination position is first found using the A* algorithm, and then, when the path needs to be changed due to an encounter with an obstacle while a robot is moving or the like, the path found before is partially modified, i.e., the path is reused, without searching the entire path again using the A* algorithm. This allows the mobile object to change its path quickly.
Though the above-described path search algorithms may reduce the search time to some extent, since the search time is reduced only to an integral multiple thereof, they still have the drawback in that the search time increases by geometric progression with an increase of a map size. This drawback still remains in the Anytime A* algorithm no matter how the best solution conditions for use in the first path search are greatly relaxed.
Further, in the Dynamic A* algorithm, a new path is required to be found whenever the destination position is changed, and, thus, it is difficult to apply the Dynamic A* algorithm to a large-sized map.